In one manner of processing (e.g., signing) an outgoing e-mail message, a communication application, employed by a given user, generates a hash (also called a “digest”) of the outgoing e-mail message and signs the hash of the outgoing e-mail message using a private key half of a public-private key pair. The signed hash of the outgoing e-mail message may then be transmitted along with the outgoing e-mail message as a signature. Upon receiving the e-mail message, the recipient may be provided with a degree of certainty that the received e-mail message originated with the given user by generating a hash of the e-mail message, decrypting the signature using a public key half of the public-private key pair and finding that the hash of the e-mail message matches the result of the decrypting.